import List from "./List";
import Deque from "../queue/Deque";
import NoElementException from "../exceptions/NoElementException";
import Obj, {equalsTo} from "../core/Obj";
import Comparator from "../utils/Comparator";
import PriorityQueue from "../queue/PriorityQueue";
import IllegalArgumentException from "../exceptions/IllegalArgumentException";
import FullCapacityException from "../exceptions/FullCapacityException";
import Collections from "../utils/Collections";
import {hashArray} from "../core/Hash";

/**
 * {@link List}和{@link Deque}接口的双重实现。
 *
 * 所有操作的执行都符合双向链表和列表的预期方法。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。
 *
 * 每个LinkedList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终不小于列表大小。当元素添加到LinkedList时，它的大小会自动增长但容
 * 量不会增长，但您可以手动增加它。
 *
 * @param E the type of elements in this list
 * @see List
 * @see Deque
 * @version 1.0
 */
export default class LinkedList<E> extends Obj implements List<E>, Deque<E> {

  /**
   * 此列表中当前存入的元素数量。
   *
   * @private
   * @version 1.0
   */
  private _size: number;

  /**
   * 此列表可以存储的元素数量。
   *
   * @private
   * @version 1.0
   */
  private _capacity: number;

  /**
   * 指向第一个元素的指针。
   *
   * @private
   * @version 1.0
   */
  private first: LinkedNode<E> | undefined;

  /**
   * 指向最后一个元素的指针。
   *
   * @private
   * @version 1.0
   */
  private last: LinkedNode<E> | undefined;

  /**
   * 构造一个具有默认元素和容量的LinkedList。
   *
   * 如果您不提供默认元素，它将不包含任何内容。
   * 如果您不提供默认容量，它会将容量设置为无限。
   *
   * @param elements 需要默认置入此列表的元素
   * @param capacity 此列表的容量
   * @throws {FullCapacityException} 这个列表无法容纳这些元素
   * @throws {IllegalArgumentException} 这个容量数字不正确
   * @version 1.0
   */
  public constructor(elements: E[] = [], capacity: number = -1) {
    super();

    if (capacity !== -1 && elements.length > capacity) {
      throw new FullCapacityException(LinkedList.name, capacity);
    }

    if (capacity < -1) {
      throw new IllegalArgumentException("capacity should be bigger than -1");
    }

    this._size = 0;
    this._capacity = capacity;
    this.first = undefined;
    this.last = undefined;

    if (elements !== undefined) {
      for (let element of elements) {
        this.addLast(element);
      }
    }
  }

  [Symbol.iterator](): Iterator<E> {
    return this.iterator();
  }

  /**
   * 将指定的元素附加到此列表的末尾。
   *
   * @param e 需要在加入此列表的元素
   * @return {boolean} 永远是true
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public add(e: E): boolean {
    this.addLast(e);
    return true;
  }

  /**
   * 在此列表中的指定位置插入指定元素。 将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）。
   *
   * @param index 要插入的索引
   * @param e 要插入的火元素
   * @throws {IndexOutOfBoundException} 索引不符合要求
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public addByIndex(index: number, e: E): void {
    const newIndex = Collections.accurateIndex(this, index);

    if (this.isFull()) {
      throw new FullCapacityException(LinkedList.name, this._capacity);
    }

    if (newIndex === this._size) {
      this.addLast(e);
    } else {
      const next = this.node(newIndex) as LinkedNode<E>;
      const pred = next.prev;
      const newNode = new LinkedNode(e, next, pred);
      next.prev = newNode;
      if (pred == undefined) {
        this.first = newNode;
      } else {
        pred.next = newNode;
      }
      this._size++;
    }
  }

  /**
   * 如果可以在不违反容量限制的情况下立即插入指定的元素，则在此列表的前面插入指定的元素，如果当前没有可用空间，则抛出
   * {@link FullCapacityException}。
   *
   * @param e 需要加入此列表的元素
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public addFirst(e: E): void {

    if (this.isFull()) {
      throw new FullCapacityException(LinkedList.name, this._capacity);
    }

    const f = this.first;
    const newNode = new LinkedNode(e, undefined, f);
    this.first = newNode;
    if (f === undefined) {
      this.last = newNode;
    } else {
      f.prev = newNode;
    }
    this._size++;
  }

  /**
   * 如果可以在不违反容量限制的情况下立即插入指定的元素，则在此列表的末尾插入指定的元素，如果当前没有可用空间，则抛出
   * {@link FullCapacityException}。
   *
   * @param e 需要加入此列表的元素
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public addLast(e: E): void {

    if (this.isFull()) {
      throw new FullCapacityException(LinkedList.name, this._capacity);
    }

    const l = this.last;
    const newNode = new LinkedNode(e, undefined, l);
    this.last = newNode;
    if (l === undefined) {
      this.first = newNode;
    } else {
      l.next = newNode;
    }
    this._size++;
  }

  /**
   * 返回此列表的容量。
   *
   * @return {number} 返回此列表的容量
   * @version 1.0
   */
  public capacity(): number {
    return this._capacity;
  }

  /**
   * 清空此列表。
   *
   * @version 1.0
   */
  public clear(): void {
    this.first = this.last = undefined;
    this._size = 0;
  }

  /**
   * 返回此列表是否包含指定的元素。
   *
   * @param e 需要查找的元素
   * @return {boolean} 如果此列表包含该元素，则返回true，否则返回false
   * @version 1.0
   */
  public contains(e: E): boolean {
    return this.indexOf(e) >= 0;
  }

  public equals(b: Obj): boolean {
    if (b instanceof LinkedList) {
      return Collections.equals(this, b);
    }
    return false;
  }

  /**
   * 返回在此列表对应索引位置的元素。
   *
   * @param index 需要取元素的索引
   * @return {E} 此列表中对饮元素位置的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public get(index: number): E {
    const newIndex = Collections.accurateIndex(this, index);
    let node = this.node(newIndex) as LinkedNode<E>;
    return node.item;
  }

  /**
   * 增加此列表的容量使其可以容纳更多的元素。
   *
   * 给出的容量必须比现有的容量更大，否则将会抛出{@link IllegalArgumentException}。当容量被设定为-1时，表示此列表容量无穷大，之后将不能再增
   * 加容量，也将不再判断容量是否充满。
   *
   * @param capacity 新的容量
   * @throws {IllegalArgumentException} 新的容量比当前容量小或容量已无法增长
   */
  public grow(capacity: number): boolean {
    if (capacity < this._capacity && capacity !== -1) {
      throw new IllegalArgumentException(
        "capacity " + capacity + " is smaller than current capacity " + this._capacity + " and is not -1");
    } else {
      this._capacity = capacity;
      return true;
    }
  }

  public hashCode(): number {
    return hashArray(this.toArray());
  }

  /**
   * 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
   *
   * @param e 与需要寻找的元素相等的元素
   * @return {number} 此列表中指定元素第一次出现的索引，如果此列表没有，则为 -1
   * @version 1.0
   */
  public indexOf(e: E): number {
    let index = -1;
    let flag = 0;
    for (let x = this.first; x != undefined; x = x.next) {
      if (equalsTo(e, x.item)) {
        index = flag;
        break;
      } else {
        flag++;
      }
    }
    return index;
  }

  /**
   * 返回此列表是否为空。
   *
   * @return {boolean} 如果此列表不包含任何元素，则返回true，否则返回false
   * @version 1.0
   */
  public isEmpty(): boolean {
    return this._size === 0;
  }

  /**
   * 返回此列表是否已满。
   *
   * @return {boolean} 如果此列表存储的元素已到达容量，则返回true，否则返回false。若容量为-1，则永远不会满容量
   */
  public isFull(): boolean {
    return this._size === this._capacity;
  }

  /**
   * 返回由列表内所有元素组成的迭代器。
   *
   * @return {Iterator<E>} 一个由列表内所有元素组成的迭代器
   * @see Iterator
   * @version 1.0
   */
  public iterator(): Iterator<E> {
    if (this.first !== undefined) {
      let cursor = this.first;
      return {
        next(): IteratorResult<E> {
          cursor = cursor.next as LinkedNode<E>;
          return {
            value: cursor.item,
            done: cursor.next === undefined
          };
        }
      };
    } else {
      throw new NoElementException(LinkedList);
    }
  }

  /**
   * 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1。
   *
   * @param e 与需要寻找的元素相等的元素
   * @return {number} 此列表中指定元素最后一次出现的索引，如果此列表没有，则为 -1
   * @version 1.0
   */
  public lastIndexOf(e: E): number {
    let index = -1;
    let flag = this._size - 1;
    for (let x = this.last; x != undefined; x = x.prev) {
      if (equalsTo(e, x.item)) {
        index = flag;
        break;
      } else {
        flag--;
      }
    }
    return index;
  }

  /**
   * 检索但不删除此列表的头部，如果此队列为空，则返回undefined。
   *
   * @return {E | undefined} 此列表的头部元素，若此队列为空则返回undefined
   * @version 1.0
   */
  public peek(): E | undefined {
    return this.peekFirst();
  }

  /**
   * 检索但不删除此列表的第一个元素，如果此列表为空，则返回 undefined。
   *
   * @return {E | undefined} 此列表的第一个元素，若此列表为空，则返回undefined
   * @version 1.0
   */
  public peekFirst(): E | undefined {
    return this.first?.item;
  }

  /**
   * 检索但不删除此列表的最后一个元素，如果此列表为空，则返回 undefined。
   *
   * @return {E | undefined} 此列表的最后一个元素，若此列表为空，则返回undefined
   * @version 1.0
   */
  public peekLast(): E | undefined {
    return this.last?.item;
  }

  /**
   * 检索并移除此列表的头部，如果此列表为空，则返回undefined。
   *
   * @return {E | undefined} 此列表的头部元素，若此列表为空则返回undefined
   * @version 1.0
   */
  public poll(): E | undefined {
    return this.peekFirst();
  }

  /**
   * 检索并删除此列表的第一个元素，如果此列表为空，则返回 undefined。
   *
   * @return {E | undefined} 此列表的第一个元素，若列表列为空，则返回undefined
   * @version 1.0
   */
  public pollFirst(): E | undefined {
    if (this.first === undefined) {
      return undefined;
    } else {
      let f = this.first;
      const element = f.item;
      const next = f.next;
      if (next === undefined) {
        this.last = undefined;
      } else {
        next.prev = undefined;
      }
      this._size--;
      return element;
    }
  }

  /**
   * 检索并删除此列表的最后一个元素，如果此列表为空，则返回 undefined。
   *
   * @return {E | undefined} 此列表的最后一个元素，若此列表为空，则返回undefined
   * @version 1.0
   */
  public pollLast(): E | undefined {
    if (this.last === undefined) {
      return undefined;
    } else {
      let l = this.last;
      const element = l.item;
      const next = l.prev;
      if (next === undefined) {
        this.first = undefined;
      } else {
        next.next = undefined;
      }
      this._size--;
      return element;
    }
  }

  /**
   * 移除此列表中所有与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从列表中被删除的元素相等的元素
   * @return {boolean} 如果有元素从列表中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public remove(e: E): boolean {
    let flag = false;
    for (let x = this.first; x !== undefined; x = x.next) {
      if (equalsTo(e, x.item)) {
        this.removeNode(x);
        flag = true;
      }
    }
    return flag;
  }

  /**
   * 移除此列表中指定位置的元素。 将任何后续元素向左移动（从它们的索引中减去一个）。
   *
   * 返回从列表中删除的元素。
   *
   * @param index 需要被删除的索引
   * @return {E} 被删除的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public removeByIndex(index: number): E {
    const newIndex = Collections.accurateIndex(this, index);
    const node = this.node(newIndex) as LinkedNode<E>;
    return this.removeNode(node);
  }

  /**
   * 使用过滤器，移除此列表中所有符合过滤器要求的元素。
   *
   * @param filter 一个lambda表达式，当表达式返回true时，表示该元素符合过滤器要求
   * @return {boolean} 如果有元素从列表中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public removeIf(filter: (e: E) => boolean): boolean {
    if (this.first !== undefined) {
      let flag = false;
      let cursor = this.first;
      do {
        if (filter(cursor.item)) {
          this.removeNode(cursor);
          flag = true;
        }
      } while (cursor.next === undefined);
      return flag;
    } else {
      return false;
    }
  }

  /**
   * 移除此列表中第一个与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从列表中被删除的元素相等的元素
   * @return {boolean} 如果有元素从列表中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public removeFirst(e: E): boolean {
    let flag = false;
    for (let x = this.first; x !== undefined; x = x.next) {
      if (equalsTo(e, x.item)) {
        this.removeNode(x);
        flag = true;
        break;
      }
    }
    return flag;
  }

  /**
   * 用指定的元素替换此列表中指定位置的元素。
   *
   * @param index 要替换的元素的索引
   * @param e 需要替换的元素
   * @return {E} 原本位于此索引的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public set(index: number, e: E): E {
    const newIndex = Collections.accurateIndex(this, index);

    const x = this.node(newIndex) as LinkedNode<E>;
    let old = x.item;
    x.item = e;
    return old;
  }

  /**
   * 返回此列表中的元素数。
   *
   * @return {number} 返回此列表中的元素数
   * @version 1.0
   */
  public size(): number {
    return this._size;
  }

  /**
   * 对列表中的元素进行升序排序。
   *
   * 若提供了比较器，将使用此比较器进行大小比较，否则使用默认的比较方式。
   *
   * @param comparator 用于比较的比较器
   * @throws {IllegalArgumentException} 如果不给出比较器，存储的元素本身也不支持比较
   * @see Comparator
   * @see ComparableObj
   * @version 1.0
   */
  public sort(comparator?: Comparator): void {
    const priorityQueue = new PriorityQueue(this.toArray(), -1, comparator);
    this.clear();

    while (!priorityQueue.isEmpty()) {
      const element = priorityQueue.poll() as E;
      this.addLast(element);
    }
  }

  /**
   * 返回此列表中指定的 fromIndex（含）和 toIndex（不含）之间的部分的视图。
   *
   * 如果 fromIndex 和 toIndex 相等，则返回的列表为空。
   *
   * 返回的列表是一个克隆列表，因此返回列表中的更改不会反映在此列表中，反之亦然。 返回的列表支持该列表支持的所有列表操作。
   *
   * @param fromIndex 子列表的起始索引（含）
   * @param endIndex 子列表的结束索引（不含）
   * @return {List<E>}此列表中指定范围的克隆列表
   * @throws {IllegalArgumentException} 索引超出范围或者起始索引大于结束索引
   * @version 1.0
   */
  public subList(fromIndex: number, endIndex: number): List<E> {

    const newFrom = Collections.accurateIndex(this, fromIndex);
    const newEnd = Collections.accurateIndex(this, endIndex);
    if (newFrom >= newEnd) {
      throw new IllegalArgumentException("from index " + fromIndex + " should be smaller than end index " + endIndex);
    }

    const linkedList: LinkedList<E> = new LinkedList();

    let cursor = this.node(newFrom) as LinkedNode<E>;

    for (let i = 0; i < newEnd - newFrom; i++) {
      linkedList.addLast(cursor.item);
      cursor = cursor.next as LinkedNode<E>;
    }

    return linkedList;
  }

  /**
   * 返回由列表内所有元素组成的数组。
   *
   * 该数组内的元素会是列表中元素的<strong>浅拷贝</strong>，因此后续对列表的操作不会影响到数组的浅层，反之亦然。
   *
   * @return {E[]} 一个由列表内所有元素组成的数组
   * @version 1.0
   */
  public toArray(): E[] {
    const array: E[] = [];
    for (let e of this) {
      array.push(e);
    }
    return array;
  }

  public toString(): string {
    return this.toArray().toString();
  }

  private node(index: number): LinkedNode<E> | undefined {
    if (index < (this._size >> 1)) {
      let x = this.first;
      for (let i = 0; i < index; i++) {
        x = x?.next;
      }
      return x;
    } else {
      let x = this.last;
      for (let i = this._size - 1; i > index; i--) {
        x = x?.prev;
      }
      return x;
    }
  }

  private removeNode(x: LinkedNode<E>): E {
    const item = x.item;
    const next = x.next;
    const prev = x.prev;

    if (prev === undefined) {
      this.first = next;
    } else {
      prev.next = next;
      x.prev = undefined;
    }

    if (next === undefined) {
      this.last = prev;
    } else {
      next.prev = prev;
      x.next = undefined;
    }

    this._size--;
    return item;
  }
}

/**
 * 链表中的每个元素都应该打包到这个类中。
 *
 * @version 1.0
 */
export class LinkedNode<E> {

  /**
   * 此节点本身对应的元素。
   *
   * @version 1.0
   */
  item: E;

  /**
   * 此节点的下一个节点，如果之后没有节点，则为 undefined。
   *
   * @version 1.0
   */
  next: LinkedNode<E> | undefined;

  /**
   * 此节点的前一个节点，如果之前没有节点，则为 undefined。
   *
   * @version 1.0
   */
  prev: LinkedNode<E> | undefined;

  /**
   * 构造一个linkedListNode，并将其前、后节点进行关联。
   *
   * @param item 该节点本身所对应的元素
   * @param next 此节点的下一个节点，如果之后没有节点，则为 undefined
   * @param prev 此节点的前一个节点，如果之前没有节点，则为 undefined
   * @version 1.0
   */
  public constructor(item: E, next: LinkedNode<E> | undefined, prev: LinkedNode<E> | undefined) {
    this.item = item;
    this.next = next;
    this.prev = prev;
  }
}
